<?php

/**
 *
 * Modified Pre-order Tree Traversal
 *
 * @author "Rodrigo Rutkoski Rodrigues, <rutkoski@gmail.com>"
 *
 */
class MPTT
{

  protected $table;

  protected $pk;

  protected $left;

  protected $right;

  protected $parent;

  protected $locks = 0;

  protected static $instances = array();

  /**
   *
   * @param $table
   * @param $pk
   * @param $parent
   * @param $left
   * @param $right
   * @return MPTT
   */
  public static function getInstance($table, $pk = 'id', $parent = 'parent_id', $left = 'left_id', $right = 'right_id')
  {
    if (! isset(self::$instances[$table])) {
      self::$instances[$table] = new MPTT($table, $pk, $parent, $left, $right);
    }

    return self::$instances[$table];
  }

  public function __construct($table, $pk = 'id', $parent = 'parent_id', $left = 'left_id', $right = 'right_id')
  {
    $this->table = $table;
    $this->pk = $pk;
    $this->parent = $parent;
    $this->left = $left;
    $this->right = $right;
  }

  public function toHierarchicalData($flat, $children = 'children')
  {
    $parents = array();

    $data = array();

    $i = 0;
    while ($i < count($flat)) {
      $row = $flat[$i++];

      $node_id = $row[$this->pk];
      $parent_id = $row[$this->parent];

      if (empty($parent_id)) {
        continue;
      }
      elseif (! isset($parents[$parent_id])) {
        $data[$node_id] = $row;
        $parents[$node_id] = & $data[$node_id];
      }
      else {
        if (! isset($parents[$parent_id][$children])) {
          $parents[$parent_id][$children] = array();
        }

        $parents[$parent_id][$children][$node_id] = $row;

        $parents[$node_id] = & $parents[$parent_id][$children][$node_id];
      }
    }

    return $data;
  }

  /**
   * Rebuild the tree using the parent id
   *
   * @return void
   */
  public function rebuild($orderBy = null, $parent_id = 0, $left_id = 1)
  {
    $dao = DAO::getInstance();

    $right_id = $left_id + 1;

    $children = $dao->from($this->table)->select($this->pk)->where("$this->parent = ?")->orderBy($orderBy)->execute(
        $parent_id)->fetchCol();

    foreach ($children as $child) {
      $right_id = $this->rebuild($orderBy, $child, $right_id);
    }

    $dao->query("UPDATE $this->table SET $this->left = ?, $this->right = ? WHERE $this->pk = ?")->execute($left_id,
        $right_id, $parent_id);

    return $right_id + 1;
  }

  public function findAllQuery($where = null)
  {
    if (! empty($where)) {
      $where = "AND $where";
    }

    $sql = "SELECT node.*, (COUNT(parent.$this->pk) - 1) AS depth
      FROM $this->table AS node, $this->table AS parent
      WHERE node.$this->left BETWEEN parent.$this->left AND parent.$this->right $where
      GROUP BY node.$this->pk ORDER BY node.$this->left
    ";

    return $sql;
  }

  public function findSubtreeQuery()
  {
    $sql = "SELECT node.*, (COUNT(parent.$this->pk) - (sub_tree.depth + 1)) AS depth
      FROM $this->table AS node, $this->table AS parent, $this->table AS sub_parent,
        (
          SELECT node.$this->pk, (COUNT(parent.$this->pk) - 1) AS depth
          FROM $this->table AS node, $this->table AS parent
          WHERE node.$this->left BETWEEN parent.$this->left AND parent.$this->right AND node.$this->pk = ?
          GROUP BY node.$this->pk ORDER BY node.$this->left
        ) AS sub_tree
      WHERE node.$this->left BETWEEN parent.$this->left AND parent.$this->right
        AND node.$this->left BETWEEN sub_parent.$this->left AND sub_parent.$this->right
        AND sub_parent.$this->pk = sub_tree.$this->pk
      GROUP BY node.$this->pk
      ORDER BY node.$this->left
    ";

    return $sql;
  }

  public function remove($id)
  {
    if ($id == 0) {
      throw new Exception("Cannot remove id 0");
    }

    $this->lock();

    $dao = DAO::getInstance();

    $data = $dao->from($this->table)->select(
        "$this->left, $this->right, $this->right - $this->left + 1 AS width, $this->parent")->where(
        "$this->pk = ?")->execute($id)->fetchRow();

    if (empty($data)) {
      throw new Exception("Row not found in table <b>$this->table</b> where <b>$this->pk</b> = <b>$id</b>");
    }

    $left_id = ( int ) sy_get_param($data, $this->left);
    $right_id = ( int ) sy_get_param($data, $this->right);
    $width = ( int ) sy_get_param($data, 'width');
    $parent_id = ( int ) sy_get_param($data, $this->parent, '0');

    $dao->query("DELETE FROM $this->table WHERE $this->left = ?")->execute($left_id);
    $dao->query("UPDATE $this->table SET $this->parent = ? WHERE $this->parent = ?")->execute($parent_id, $id);
    $dao->query(
        "UPDATE $this->table SET $this->right = $this->right - 1, $this->left = $this->left - 1 WHERE $this->left BETWEEN ? AND ?")->execute(
        $left_id, $right_id);
    $dao->query("UPDATE $this->table SET $this->right = $this->right - 2 WHERE $this->right > ?")->execute($right_id);
    $dao->query("UPDATE $this->table SET $this->left = $this->left - 2 WHERE $this->left > ?")->execute($right_id);

    $this->unlock();
  }

  public function removeBranch($id)
  {
    if ($id == 0) {
      throw new Exception("Cannot remove id 0");
    }

    $this->lock();

    $dao = DAO::getInstance();

    $data = $dao->from($this->table)->select(
        "$this->left, $this->right, $this->right - $this->left + 1 AS width, $this->parent")->where(
        "$this->pk = ?")->execute($id)->fetchRow();

    if (empty($data)) {
      throw new Exception("Row not found in table <b>$this->table</b> where <b>$this->pk</b> = <b>$id</b>");
    }

    $left_id = ( int ) sy_get_param($data, $this->left);
    $right_id = ( int ) sy_get_param($data, $this->right);
    $width = ( int ) sy_get_param($data, 'width');
    $parent_id = ( int ) sy_get_param($data, $this->parent, '0');

    $dao->query("DELETE FROM $this->table WHERE $this->left BETWEEN ? AND ?")->execute($left_id, $right_id);
    $dao->query("UPDATE $this->table SET $this->right = $this->right - ? WHERE $this->right > ?")->execute($width, $right_id);
    $dao->query("UPDATE $this->table SET $this->left = $this->left - ? WHERE $this->left > ?")->execute($width, $right_id);

    $this->unlock();
  }

  public function numChildren($id)
  {
    $dao = DAO::getInstance();

    $sql = "SELECT (node.$this->right - node.$this->left - 1) / 2 FROM $this->table AS node WHERE node.$this->pk = ?";

    $num = $dao->query($sql)->execute($id)->fetchOne();

    return ( int ) $num;
  }

  public function before($id, &$data)
  {
    if ($id == 0) {
      throw new Exception("Cannot add before id 0");
    }

    $dao = DAO::getInstance();

    $this->lock();

    $left_id = $dao->from($this->table)->select($this->left)->where("$this->pk = ?")->execute($id)->fetchOne();

    if (is_null($left_id)) {
      throw new Exception("Row not found in table <b>$this->table</b> where <b>$this->pk</b> = <b>$id</b>");
    }

    $dao->query("UPDATE $this->table SET $this->right = $this->right + 2 WHERE $this->right >= ?")->execute($left_id);
    $dao->query("UPDATE $this->table SET $this->left = $this->left + 2 WHERE $this->left >= ?")->execute($left_id);

    $parent_id = $dao->from($this->table)->select($this->parent)->where("$this->pk = ?")->execute($id)->fetchOne();

    $data[$this->parent] = $parent_id;
    $data[$this->left] = $left_id;
    $data[$this->right] = $left_id + 1;

    $this->insert($data);

    $this->unlock();
  }

  public function after($id, &$data)
  {
    if ($id == 0) {
      throw new Exception("Cannot add after id 0");
    }

    $dao = DAO::getInstance();

    $this->lock();

    $right_id = $dao->from($this->table)->select($this->right)->where("$this->pk = ?")->execute($id)->fetchOne();

    if (is_null($right_id)) {
      throw new Exception("Row not found in table <b>$this->table</b> where <b>$this->pk</b> = <b>$id</b>");
    }

    $dao->query("UPDATE $this->table SET $this->right = $this->right + 2 WHERE $this->right > ?")->execute($right_id);
    $dao->query("UPDATE $this->table SET $this->left = $this->left + 2 WHERE $this->left > ?")->execute($right_id);

    $parent_id = $dao->from($this->table)->select($this->parent)->where("$this->pk = ?")->execute($id)->fetchOne();

    $data[$this->parent] = $parent_id;
    $data[$this->left] = $right_id + 1;
    $data[$this->right] = $right_id + 2;

    $this->insert($data);

    $this->unlock();
  }

  public function append($id, &$data)
  {
    $dao = DAO::getInstance();

    $this->lock();

    if ($id == 0) {
      $right_id = $dao->from($this->table)->select("MAX($this->right)")->execute()->fetchOne();
      $right_id = $right_id + 1;
    }
    else {
      $right_id = $dao->from($this->table)->select($this->right)->where("$this->pk = ?")->execute($id)->fetchOne();

      if (is_null($right_id)) {
        throw new Exception("Row not found in table <b>$this->table</b> where <b>$this->pk</b> = <b>$id</b>");
      }

      $dao->query("UPDATE $this->table SET $this->right = $this->right + 2 WHERE $this->right >= ?")->execute(
          $right_id);
      $dao->query("UPDATE $this->table SET $this->left = $this->left + 2 WHERE $this->left >= ?")->execute($right_id);
    }

    $data[$this->parent] = $id;
    $data[$this->left] = $right_id;
    $data[$this->right] = $right_id + 1;

    $this->insert($data);

    $this->unlock();
  }

  public function prepend($id, &$data)
  {
    $this->lock();

    $dao = DAO::getInstance();

    $left_id = 0;

    if ($id != 0) {
      $left_id = $dao->from($this->table)->select($this->left)->where("$this->pk = ?")->execute($id)->fetchOne();

      if (is_null($left_id)) {
        throw new Exception("Row not found in table <b>$this->table</b> where <b>$this->pk</b> = <b>$id</b>");
      }
    }

    $dao->query("UPDATE $this->table SET $this->right = $this->right + 2 WHERE $this->right > ?")->execute($left_id);
    $dao->query("UPDATE $this->table SET $this->left = $this->left + 2 WHERE $this->left > ?")->execute($left_id);

    $data[$this->left] = $left_id + 1;
    $data[$this->right] = $left_id + 2;

    $this->insert($data);

    $this->unlock();
  }

  public function move($id, $to, $pos = 'after')
  {
    if ($id == $to) {
      throw new Exception("Both ids cannot be equal");
    }

    $dao = DAO::getInstance();

    $is_child = $dao->query(
        "SELECT b.$this->left BETWEEN a.$this->left AND a.$this->right
      FROM $this->table a, $this->table b WHERE a.$this->pk = ? AND b.$this->pk = ?
    ")->execute($id, $to)->fetchOne();

    if ($is_child) {
      throw new Exception("Cannot move a node into one of it's children");
    }

    $this->lock();

    $dao = DAO::getInstance();

    $data = $dao->from($this->table)->select("$this->left, $this->right")->where("$this->pk = ?")->execute($id)->fetchRow();

    if (empty($data)) {
      throw new Exception("Row not found in table <b>$this->table</b> where <b>$this->pk</b> = <b>$id</b>");
    }

    $left_id = ( int ) sy_get_param($data, $this->left);
    $right_id = ( int ) sy_get_param($data, $this->right);

    $data = $dao->from($this->table)->where("$this->left BETWEEN ? AND ?")->execute($left_id, $right_id)->fetchAll();

    $this->remove($id, false);

    $row = array_shift($data);

    switch ($pos) {
      case 'after' :
        $this->after($to, $row);
        break;
      case 'before' :
        $this->before($to, $row);
        break;
      case 'first' :
        $this->prepend($to, $row);
        break;
      case 'last' :
        $this->append($to, $row);
        break;
    }

    while (count($data)) {
      $row = array_shift($data);
      $this->append($row[$this->parent], $row);
    }

    $this->unlock();
  }

  protected function insert(&$data)
  {
    $this->lock();

    $keys = array();
    $values = array();
    $cards = array();

    foreach ($data as $k => $v) {
      $keys[] = $k;
      $values[] = $v;
      $cards[] = '?';
    }

    $keys = implode(', ', $keys);
    $cards = implode(', ', $cards);

    DAO::getInstance()->query("INSERT INTO $this->table ($keys) VALUES ($cards)")->execute($values);

    sy_set_param($data, $this->pk, DAO::getInstance()->lastInsertID());

    $this->unlock();
  }

  protected function lock()
  {
    if ($this->locks == 0) {
      DAO::getInstance()->query("LOCK TABLE $this->table WRITE")->executeRaw();
    }

    $this->locks ++;
  }

  protected function unlock()
  {
    $this->locks --;

    if ($this->locks == 0) {
      DAO::getInstance()->query("UNLOCK TABLES")->executeRaw();
    }
  }

}

?>